package 链表系列;

public class ReverseList {
    //迭代法（双指针法）
//    public ListNode reverseList(ListNode head) {
//        ListNode cur = head;
//        ListNode prev = null;
//        ListNode temp = null;
//        while( cur != null){
//            temp = cur.next;    // 保存下一节点
//            cur.next = prev;    // 当前节点的下一节点指向前一个节点
//            prev = cur;         // 前一个节点指向当前节点
//            cur = temp;         // 当前节点指向下一个节点
//        }
//        return prev;            //返回最后一个节点
//    }

    //递归法
    //从前先后递归
//    public ListNode reverseList(ListNode head){
//        return reverse(null,head);
//    }
//    private ListNode reverse(ListNode prev, ListNode cur){
//        if (cur == null) {
//            return prev;
//        }
//        ListNode temp = null;
//        temp = cur.next;    // 先保存下一个节点
//        cur.next = prev;    // 反转
//        // 更新prev、cur位置
//        // prev = cur；
//        // cur = temp
//        return reverse(cur, temp);
//    }

    //从后向前递归
    //以链表1->2->3->4->5为例
    public ListNode reverseList(ListNode head){
        //边缘条件判断
        if(head == null) return null;
        if(head.next == null) return head;      //到5这个节点，它的下一个节点为空，返回5这个节点

        //递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next); //从一开始一直递归直到走到4，有返回值，返回的是5这个节点
        //翻转头节点与第二个节点的指向
        head.next.next = head;  //此时head为值为4的这个节点，然后4的下一个是5，令5的下一个指向4，实现翻转，以此类推
        //此时的head节点为尾节点，next需要指向null
        head.next = null;       //此时head为4，断掉head指向5的指针，以此类推
        return last;    //一直返回5这个节点
    }
}
